const { swap } = require('./公共js方法')

function quickSort(arr) {
    _quickSort(arr, 0, arr.length - 1)
}

// 对arr[l,...r]进行快速排序
function _quickSort(arr, l, r) {
    if (l >= r) return
    let p = _partition(arr, l, r)
    _quickSort(arr, l, p - 1)
    _quickSort(arr, p + 1, r)
}

// 返回p，使得arr[l,...p-1] < arr[p], arr[p+1,...r] > arr[p]
function _partition(arr, l, r) {

    let j = l
    // arr[l + 1, ...j] < arr[l], arr[j + 1,...r] > arr[l]
    for (let i = l; i <= r; i++) {
        if (arr[i] < arr[l]) {
            swap(arr, j + 1, i)
            j++
        }
    }
    swap(arr, j,l)
    return j
}

let arr = [8,7,9,5,4,1,3,54,1,0,-1]
quickSort(arr)
console.log(arr)